8、杨辉三角形
题目 杨辉三角形
思路分析
以为会是数字三角形模型的线性dp 但看到这个数据范围 n最大1e9 emm dp应该是不可能了
这得线性的算法啊 搞不懂
找一下规律先吧
要不能构造多少是多少 拿一部分分
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N];
int main()
{
for(int i=1;i<10;i++){
for(int j=1;j<=i;j++){
if(i==1)
f[i][j]=1;
else if(j==1)
f[i][j]=1;
else if(i==j)
f[i][j]=1;
else
f[i][j]=f[i-1][j-1]+f[i-1][j];
cout<<f[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
貌似是没问题的
那然后就是 尽可能枚举多一点 然后枚举到第一个输入的n的时候停止
计算一下它是第几个数
前面分析出来了
(curi,curi)是第 (1+curi)*curi/2个数 (curi,cury)是第 (1+curi)*curi/2 - (curi-curj)个数
所以可以写成
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N];
int main()
{
int x;cin>>x;
int curi,curj;
for(int i=1;i<10;i++){
bool success=false;
for(int j=1;j<=i;j++){
if(i==1)
f[i][j]=1;
else if(j==1)
f[i][j]=1;
else if(i==j)
f[i][j]=1;
else
f[i][j]=f[i-1][j-1]+f[i-1][j];
// cout<<f[i][j]<<" ";
if(f[i][j]==x){
curi=i,curj=j;
success=true;
break;
}
}
// cout<<endl;
if(success)
break;
}
//(curi,curi)是第 (1+curi)*curi/2个数 (curi,cury)是第 (1+curi)*curi/2 - (curi-curj)个数
cout<< (1+curi)*curi/2 - (curi-curj);
return 0;
}
拿6试了一下 对了
那就这样了 把枚举范围放大一些 但别太贪小心爆空间 一分没有
最后是过了4个 8分 也还行 将近两道填空了呢
至于正解 大概看了一下 好像是因为有左右对称 然后可以只枚举一半
/* 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
可以发现找到第一个出现的一定在左边故右边可以直接删去
1
1 2
1 3
1 4 6
1 5 10
1 6 15 20
/ / / /
从打斜杠的地方可以发现规律为C(2n,n)
故找到最大的斜行
用t来代表斜行数
最大为1e9；
故求有多少个斜行数满足？
int x;//记录第几个斜行满足
for(int t=0;;t++){
if(1e9<=C(2t,t)){
x=t;
break;
}
}
故解得t=17;
斜线从大到小依次排列第一找到第一个数
再通过二分查找
C(t, k)对应的顺序值为：(t + 1) * t / 2 + k + 1
想不到呢 知足了
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N];
int main()
{
int x;cin>>x;
int curi,curj;
for(int i=1;i<N;i++){
bool success=false;
for(int j=1;j<=i;j++){
if(i==1)
f[i][j]=1;
else if(j==1)
f[i][j]=1;
else if(i==j)
f[i][j]=1;
else
f[i][j]=f[i-1][j-1]+f[i-1][j];
// cout<<f[i][j]<<" ";
if(f[i][j]==x){
curi=i,curj=j;
success=true;
break;
}
}
// cout<<endl;
if(success)
break;
}
//(curi,curi)是第 (1+curi)*curi/2个数 (curi,cury)是第 (1+curi)*curi/2 - (curi-curj)个数
cout<< (1+curi)*curi/2 - (curi-curj);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
LL C(int x,int k){
LL ans=1;
for(int i=x,j=1;j<=k;i--,j++){
ans=ans*i/j;
if(ans>n)return ans;
}
return ans;
}
bool check(int x){
LL l=2*x,r=max(n,l);
while(l<r){
int mid=l+r>>1;
if(C(mid,x)>=n)r=mid;
else l=mid+1;
}
if(C(r,x)!=n)return false;
cout<<(LL)(r+1)*r/2+x+1<<endl;
return true;
}
int main(){
cin>>n;
for(int t=17;;t--){
if(check(t))break;
}
return 0;
}
💬 评论